// 最好的时间复杂度O(logn), 最坏情况：O(n^2)
export default function quickSort(arr: number[]): number[] {
  partition(0, arr.length - 1);

  function partition(left: number, right: number) {
    if (left >= right) return;

    // 1. 找到基准元素
    const pivot = arr[right];
    let i = left;
    let j = right - 1;

    while (i <= j) {
      while (arr[i] < pivot) {
        i++;
      }
      while (arr[j] > pivot) {
        j--;
      }

      // 说明已经找到比pivot小的元素和比pivot大的元素
      if (i <= j) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
        i++;
        j--;
      }
    }
    // 完成后将pivot放到正确的位置
    [arr[i], arr[right]] = [arr[right], arr[i]];

    // 左右继续调用
    partition(left, j);
    partition(i + 1, right);
  }

  return arr;
}

console.log(quickSort([12, 232, 43, 12, 423, 1, 2, 3]));
